from collections import deque
from typing import List, Optional

from python.mypackage import TreeNode


class Solution:
    """
    方法： levelOrder 使用BFS进行二叉树的层序遍历
    
    Args:
        root (Optional[TreeNode]): 二叉树的根节点
        
    Returns:
        List[List[int]]: 层序遍历结果,每个子列表包含同一层的节点值
        
    Time:  
        O(N)，其中 N 为二叉树的节点数。每个节点只会被访问一次。
        
    Space:  
        O(W)，其中 W 为二叉树的最大宽度。在最坏情况下，队列中会存储一层中的所有节点。
    """
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        ans = []
        cur = [root]
        while cur:
            nxt = []
            vals = []
            for node in cur:
                vals.append(node.val)
                if node.left: nxt.append(node.left)
                if node.right: nxt.append(node.right)
            cur = nxt
            ans.append(vals)
        return ans
    
    """
    方法： levelOrder2 使用队列进行二叉树的层序遍历
    
    Args:
        root (Optional[TreeNode]): 二叉树的根节点
        
    Returns:
        List[List[int]]: 层序遍历结果,每个子列表包含同一层的节点值
        
    Time:  
        O(N)，其中 N 为二叉树的节点数。每个节点只会被访问一次。
        
    Space:  
        O(W)，其中 W 为二叉树的最大宽度。在最坏情况下，队列中会存储一层中的所有节点。
    """
    def levelOrder2(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        ans = []
        queue = deque([root])
        while queue:
            level = []
            level_size = len(queue)
            for _ in range(level_size):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            ans.append(level)
        return ans
    def levelOrder1(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        ans = []
        queue = deque([root])
        while queue:
            vals = []
            for _ in range(len(queue)):
                node = queue.popleft()
                vals.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            ans.append(vals)
        return ans